Reconfigurable logic (RL) is used to implement functions which are unknown at the design time. To enable this reconfigurable logic architectures are made generic in the sense that various logic functions can be mapped onto them. Although this offers flexibility to a user, at the same time it leads to a large area overhead compared with the logic which would be required for a standard ASIC implementation, for example. Because of this, a basic computational element of traditional reconfigurable logic devices (such as field programmable gate arrays (FPGAs)), the so called logic cell, contains only a limited amount of logic resources, e.g. look-up tables. Moreover, the resources of a logic cell are chosen in such a way that they reflect the common requirements of different applications. However, if coarser or more specialised functions are to be mapped, usually either much more logic cells are required or such functions cannot be mapped at all.
Reconfigurable logic devices comprise data flow controlling elements such as multiplexers, demultiplexers, gates etc and dataflow manipulating elements, such as logical gates, adders and lookup tables. The latter allow implementation of various functions, which can be redefined easily by loading them with a different content. Reconfigurable logic devices further comprise configuration memory units (configuration memory) for storing settings of data flow controlling elements, such as multiplexers, demultiplexers, switches etc. In this way connections between different parts of the reconfigurable processing unit can be rapidly redefined. Control signals for the memory cells are generated by an address decoder in response to an address offered at the input thereof.
In particular multiplexers of different sizes and with different operand widths are heavily used in random logic as well as data-path applications. Despite that, in a large majority of traditional reconfigurable logic architectures, there is support for the implementation of small multiplexers only. This limitation has two reasons:
1. A specific type of a logic cell which hampers a multiplexer implementation.
2. A limited number of logic cell inputs which causes that a logic cell cannot obtain a required number of signals from the routing resources.
For applications, in which wide multiplexers are heavily used (e.g. DSP data-paths, cryptography, networking), this is an important limitation. Although, this is particularly an issue for architectures with multi-bit output LUTs (moLUTs), any current FPGAs, both fine- and coarse-grained, face this problem in some way.